package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-06 15:35
 **/
public class LeetCode312 {

    //动态规划
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] momo = new int[n + 2][n + 2];
        int[] val = new int[n + 2];
        val[0] = 1;
        val[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }

        //从右往左,先计算小区间,再计算大区间
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 2; j < n + 2; ++j) {
                for (int k = i + 1; k < j; ++k) {
                    int sum = val[i] * val[k] * val[j];
                    sum += momo[i][k] + momo[k][j];
                    momo[i][j] = Math.max(momo[i][j], sum);
                }
            }
        }
        return momo[0][n + 1];
    }


    //记忆化搜索
    /*//用来记录(left, right)区间能获取硬币的最大数量
    int[][] memo;
    int[] val;

    public int maxCoins(int[] nums) {
        int n = nums.length;
        //0和n + 1为边界,置其值为1,1 - n值对应0 - n - 1编号气球的数字
        val = new int[n + 2];
        for (int i = 1; i <= n; ++i) {
            val[i] = nums[i - 1];
        }
        val[0] = 1;
        val[n + 1] = 1;

        memo = new int[n + 2][n + 2];
        //初始化记忆数组
        for (int i = 0; i < n + 2; ++i) {
            Arrays.fill(memo[i], -1);
        }

        return solve(0, n + 1);
    }

    //计算(left, right)区间能获取硬币的最大数量
    int solve(int left, int right) {
        //left >= right - 1,区间内没有气球,直接返回0
        if (left >= right - 1) {
            return 0;
        }

        //如果已经记录过该区间的值,直接返回
        if (memo[left][right] != -1) {
            return memo[left][right];
        }

        //记算该区间能获取硬币的最大数量,即(k ∈ [left + 1, right - 1]),计算max(val[left] * val[i] * val[right] + solve(left,i) + solve(i, right))
        for (int i = left + 1; i < right; ++i) {
            int sum = val[i] * val[left] * val[right];
            sum += solve(left, i) + solve(i, right);
            memo[left][right] = Math.max(memo[left][right], sum);
        }

        return memo[left][right];
    }*/


}
